Typical DP Contest E - 数

解答
d = int(input())
n = input()
MOD = 1000000007
# dp[i][j][m] := 上からi桁目を決める段階、今作成している数字の桁和をDで割った余りがj、今作成している数字が n 未満であることが確定しているかどうか(している場合は1)
dp = [[[0 for _ in range(2)] for _ in range(105)] for _ in range(10005)]
dp[0][0][0] = 1
for i in range(1, len(n) + 1):
for j in range(d):
for k in range(10):
# i−1桁目まで決めた段階での桁和をDで割った余りがjのとき、i桁目をk(0 <= k <= 9)にすることを考える
now = int(n[i - 1])
if now > k:
# i−1桁目を決める時点でN未満であることが確定しているかどうかにかかわらず、
# i+1桁目以降でどんな数字を当てはめてもN未満になる
dp[i][(j + k) % d][1] += (dp[i - 1][j][0] + dp[i - 1][j][1]) % MOD
dp[i][(j + k) % d][1] %= MOD
elif now == k:
# N未満が確定しているかどうかは、i−1桁目の時点でN未満であることが確定しているかどうかに依存
dp[i][(j + k) % d][1] += dp[i - 1][j][1]
dp[i][(j + k) % d][0] += dp[i - 1][j][0]
dp[i][(j + k) % d][1] %= MOD
dp[i][(j + k) % d][0] %= MOD
else:
# N未満であることがi−1桁目の時点で決まっていれば良いが、
# そうでない場合は、i桁目でkを選ぶとNを超えてしまうので、問題の条件を満たさなくなる
dp[i][(j + k) % d][1] += dp[i - 1][j][1]
dp[i][(j + k) % d][1] %= MOD
# 正整数が条件なので、0を省く
print((dp[len(n)][0][0] + dp[len(n)][0][1] - 1) % MOD)

テーマ

メモ

提出

d = int(input())
n = int(input())
# dp[i] := i の各桁の数の和
# i <= pow(10, 100000) TLE
# dp[i] := i の倍数であるものの個数
dp = [0] * (100 + 1)

Related